struct DListNode {
    int key;
    int val;
    DListNode* next;
    DListNode* prev;
    DListNode(int k = -1, int e = -1)
        : key(k), val(e), next(nullptr), prev(nullptr) {}
};

class LRUCache {
public:
    LRUCache(int capacity) {
        _capacity = capacity;
        head = new DListNode();
        tail = new DListNode();
        head->next = tail;
        head->prev = tail;
        tail->next = head;
        tail->prev = head;
    }

    int get(int key) {
        if (!mp.count(key))
            return -1;
        else {
            DListNode* cur = mp[key];
            if (cur->prev == head) {
                return mp[key]->val;
            }
            // DListNode* _pre = cur->prev;
            // DListNode* _next = cur->next;
            // _pre->next = _next;
            // _next->prev = _pre;

            // cur->next = head->next;
            // cur->prev = head;
            // head->next->prev = cur;
            // head->next = cur;
            // return mp[key]->val;

            adjust(cur);
            return mp[key]->val;
        }
    }

    void put(int key, int value) {
        if (mp.count(key)) {
            mp[key]->val = value;
            adjust(mp[key]);
            return;
        }

        DListNode* newnode = new DListNode(key, value);
        mp[key] = newnode;

        newnode->next = head->next;
        newnode->prev = head;
        head->next->prev = newnode;
        head->next = newnode;

        ++_size;
        if (_size > _capacity) {
            DListNode* del = tail->prev;
            tail->prev = del->prev;
            del->prev->next = tail;
            mp.erase(del->key);
            delete del;
            del = nullptr;
            --_size;
        }
    }

    void adjust(DListNode* cur) {
        DListNode* _pre = cur->prev;
        DListNode* _next = cur->next;
        _pre->next = _next;
        _next->prev = _pre;

        cur->next = head->next;
        cur->prev = head;
        head->next->prev = cur;
        head->next = cur;
    }

private:
    unordered_map<int, DListNode*> mp;
    DListNode* head;
    DListNode* tail;
    int _size = 0;
    int _capacity;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */